<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>

</body>
<script>

    let nums = [2, 2, 1, 1, 1, 2, 2]
    let maxNums = majorityElement5(nums)
    console.log(maxNums);

    //排序算法
    function majorityElement(nums) {
        nums.sort((a, b) => a - b);
        return nums[Math.floor(nums.length / 2)]
    };

    //map算法
    function majorityElement2(nums) {
        let map = new Map()
        for (let i = 0; i < nums.length; i++) {
            if (map.has(nums[i])) {
                map.set(nums[i], map.get(nums[i]) + 1);
            } else {
                map.set(nums[i], 1);
            }
        }
        let maxKey
        let maxValue = 0
        for (const [key, value] of map) {
            if (maxValue) {
                if (maxValue < value) {
                    maxValue = value
                    maxKey = key
                }
            } else {
                maxValue = value
                maxKey = key
            }
        }
        return maxKey
    };

    //随机算法
    function majorityElement3(nums) {
        while (true) {
            let index = getRandomInt(0, nums.length - 1)
            if (count(nums, nums[index]) > (nums.length / 2)) {
                return nums[index]
            }
        }
    };

    function getRandomInt(min, max) {
        // 确保 min 和 max 是整数且 min < max
        min = Math.ceil(min); // 向上取整
        max = Math.floor(max); // 向下取整
        return Math.floor(Math.random() * (max - min + 1)) + min; // 生成随机整数
    }

    function count(nums, num) {
        let count = 0
        for (let i = 0; i < nums.length; i++) {
            if (nums[i] === num) {
                count++
            }
        }
        return count
    }

    //分治算法
    function majorityElement4(nums) {
        return partition(nums, 0, nums.length - 1)
    };

    function partition(nums, min, max) {
        if (min === max) {
            return nums[min]
        }

        mid = Math.floor((min + max) / 2)
        let left = partition(nums, min, mid)
        let right = partition(nums, mid + 1, max)
        if (left === right) {
            return left
        }

        let leftCount = count(nums, left)
        let rightCount = count(nums, right)

        return leftCount > rightCount ? left : right
    }

    //Boyer-Moore 投票算法
    function majorityElement5(nums) {
        var MaxNums
        var count = 0
        for (let i = 0; i < nums.length; i++) {
            if (count === 0) {
                MaxNums = nums[i]
                count++
            } else {
                count--
            }
        }
        return MaxNums
    };
</script>

</html>